home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / agrep / asplit.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  13.8 KB  |  483 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. #include "agrep.h"
  4.  
  5. extern int checksg();
  6. extern int D;
  7. extern FILE *debug;
  8.  
  9. /* All borrowed from agrep.c and are needed for searching the index */
  10. extern    ParseTree aterminals[MAXNUM_PAT];
  11. extern int    AComplexBoolean;
  12.  
  13. /* returns where it found the distinguishing token: until that from prev value of begin is the current pattern (not just the "words" in it) */
  14. CHAR *
  15. aparse_flat(begin, end, prev, next)
  16.     CHAR    *begin;
  17.     CHAR    *end;
  18.     int    prev;
  19.     int    *next;
  20. {
  21.     if (begin > end) {
  22.         *next = prev;
  23.         return end;
  24.     }
  25.  
  26.     if (prev & ENDSUB_EXP) prev &= ~ATTR_EXP;
  27.     if ((prev & ATTR_EXP) && !(prev & VAL_EXP)) prev |= VAL_EXP;
  28.  
  29.     while (begin <= end) {
  30.         if (*begin == ',') {
  31.             prev |= OR_EXP;
  32.             prev |= VAL_EXP;
  33.             prev |= ENDSUB_EXP;
  34.             if (prev & AND_EXP) {
  35.                 fprintf(stderr, "parse error at character '%c'\n", *begin);
  36.                 return NULL;
  37.             }
  38.             *next = prev;
  39.             return begin;
  40.         }
  41.         else if (*begin == ';') {
  42.             prev |= AND_EXP;
  43.             prev |= VAL_EXP;
  44.             prev |= ENDSUB_EXP;
  45.             if (prev & OR_EXP) {
  46.                 fprintf(stderr, "parse error at character '%c'\n", *begin);
  47.                 return NULL;
  48.             }
  49.             *next = prev;
  50.             return begin;
  51.         }
  52.         else if (*begin == '\\') begin ++;    /* skip two things */
  53.         begin++;
  54.     }
  55.  
  56.     *next = prev;
  57.     return begin;
  58. }
  59.  
  60. int
  61. asplit_pattern_flat(APattern, AM, terminals, pnum_terminals, pAParse)
  62.     CHAR    *APattern;
  63.     int    AM;
  64.     ParseTree terminals[MAXNUM_PAT];
  65.     int    *pnum_terminals;
  66.     int    *pAParse;
  67. {
  68.     CHAR  *buffer;
  69.     CHAR  *buffer_pat;
  70.     CHAR  *buffer_end;
  71.  
  72.     buffer = APattern;
  73.     buffer_end = buffer + AM;
  74.     *pAParse = 0;
  75.  
  76.     /*
  77.      * buffer is the runnning pointer, buffer_pat is the place where
  78.      * the distinguishing delimiter was found, buffer_end is the end.
  79.      */
  80.      while (buffer_pat = aparse_flat(buffer, buffer_end, *pAParse, pAParse)) {
  81.         /* there is no pattern until after the distinguishing delimiter position: some agrep garbage */
  82.         if (buffer_pat <= buffer) {
  83.             buffer = buffer_pat+1;
  84.             if (buffer_pat >= buffer_end) break;
  85.             continue;
  86.         }
  87.         if (*pnum_terminals >= MAXNUM_PAT) {
  88.             fprintf(stderr, "boolean expression has too many terms\n");
  89.             return -1;
  90.         }
  91.         terminals[*pnum_terminals].op = 0;
  92.         terminals[*pnum_terminals].type = LEAF;
  93.         terminals[*pnum_terminals].terminalindex = *pnum_terminals;
  94.         terminals[*pnum_terminals].data.leaf.attribute = 0;    /* default is no structure */
  95.         terminals[*pnum_terminals].data.leaf.value = (CHAR *)malloc(buffer_pat - buffer + 2);
  96.         memcpy(terminals[*pnum_terminals].data.leaf.value, buffer, buffer_pat - buffer);    /* without distinguishing delimiter */
  97.         terminals[*pnum_terminals].data.leaf.value[buffer_pat - buffer] = '\0';
  98.         (*pnum_terminals)++;
  99.         if (buffer_pat >= buffer_end) break;
  100.         buffer = buffer_pat+1;
  101.     }
  102.     if (buffer_pat == NULL) return -1;    /* got out of while loop because of NULL rather than break */
  103.     return(*pnum_terminals);
  104. }
  105.  
  106. int
  107. is_complex_boolean(buffer, len)
  108.     CHAR    *buffer;
  109.     int    len;
  110. {
  111.     int    i = 0;
  112.     CHAR    cur = '\0';
  113.  
  114.     while (i < len) {
  115.         if (buffer[i] == '\\') i+=2;
  116.         else if (buffer[i] == ',') {
  117.             if ((cur == ';') || (cur == '~')) return 1;
  118.             else cur = ',';
  119.             i++;
  120.         }
  121.         else if (buffer[i] == ';') {
  122.             if ((cur == ',') || (cur == '~')) return 1;
  123.             else cur = ';';
  124.             i++;
  125.         }
  126.         /* else if ((buffer[i] == '~') || (buffer[i] == '{') || (buffer[i] == '}')) { */
  127.         else if (buffer[i] == '~') {
  128.             /* even if pattern has just ~s... user must use -v option for single NOT */
  129.             return 1;
  130.         }
  131.         else i++;
  132.     }
  133.     return 0;
  134. }
  135.  
  136. /* The possible tokens are: ; , a e ~ { } */
  137. int
  138. get_token_bool(buffer, len, ptr, tokenbuf, tokenlen)
  139.     CHAR    *buffer, *tokenbuf;
  140.     int    len, *ptr, *tokenlen;
  141. {
  142.     if ((*ptr>=len) || (buffer[*ptr] == '\n') || (buffer[*ptr] == '\0')) return 'e';
  143.     while ((*ptr<len) && (buffer[*ptr] != '\n') && (buffer[*ptr] != '\0') && ((buffer[*ptr] == ' ') || (buffer[*ptr] == '\t'))) (*ptr)++;
  144.     if ((*ptr>=len) || (buffer[*ptr] == '\n') || (buffer[*ptr] == '\0'))  return 'e';
  145.     if ((buffer[*ptr] == ',') || (buffer[*ptr] == ';') || (buffer[*ptr] == '~') || (buffer[*ptr] == '{') || (buffer[*ptr] == '}')) {
  146.         tokenbuf[0] = buffer[*ptr];
  147.         *tokenlen = 1;
  148.         return buffer[(*ptr)++];
  149.     }
  150.     *tokenlen = 0;
  151.     if (buffer[*ptr] == '\\') {
  152.         tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  153.         tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  154.     }
  155.     else tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  156.     while (    (*ptr<len) && (buffer[*ptr] != '\n') && (buffer[*ptr] != '\0') &&
  157.         (buffer[*ptr] != ',') && (buffer[*ptr] != ';') && (buffer[*ptr] != '~') && (buffer[*ptr] != '{') && (buffer[*ptr] != '}')) {
  158.         if (buffer[*ptr] == '\\') {
  159.             tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  160.             tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  161.         }
  162.         else tokenbuf[(*tokenlen)++] = buffer[(*ptr)++];
  163.     }
  164.     tokenbuf[*tokenlen] = '\0';
  165.     return 'a';
  166.     /* It will return next 'e' next time if we broke out of the loop because (*ptr >= len) */
  167. }
  168.  
  169. print_tree(t, level)
  170.     ParseTree *t;
  171. {
  172.     int    i;
  173.  
  174.     if (t == NULL) printf("NULL");
  175.     else if (t->type == LEAF) {
  176.         for (i=0; i<level; i++) printf("  ");
  177.         printf("LEAF %x %x %s\n", t->op, t->terminalindex, t->data.leaf.value);
  178.     }
  179.     else if (t->type == INTERNAL) {
  180.         if (t->data.internal.left != NULL) print_tree(t->data.internal.left, level + 1);
  181.         for (i=0; i<level; i++) printf("  ");
  182.         printf("INTERNAL %x\n", t->op);
  183.         if (t->data.internal.right != NULL) print_tree(t->data.internal.right, level + 1);
  184.     }
  185. }
  186.  
  187. destroy_tree(t)
  188.     ParseTree *t;
  189. {
  190.     if (t == NULL) return;
  191.     if (t->type == LEAF) {
  192.         free(t->data.leaf.value);    /* t itself should not be freed: static allocation */
  193.     }
  194.     else if (t->type == INTERNAL) {
  195.         if (t->data.internal.left != NULL) destroy_tree(t->data.internal.left);
  196.         if (t->data.internal.right != NULL) destroy_tree(t->data.internal.right);
  197.         free(t);
  198.     }
  199. }
  200.  
  201. /*
  202.  * Recursive descent; C-style => AND + OR have equal priority => must bracketize expressions appropriately or will go left->right.
  203.  * Grammar:
  204.  *     E = {E} | ~a | ~{E} | E ; E | E , E | a
  205.  * Parser:
  206.  *    One look ahead at each literal will tell you what to do.
  207.  *    ~ has highest priority, ; and , have equal priority (left to right associativity), ~~ is not allowed.
  208.  */
  209. ParseTree *
  210. aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)
  211.     CHAR    *buffer;
  212.     int    len;
  213.     int    *bufptr;
  214.     ParseTree terminals[];
  215.     int    *pnum_terminals;
  216. {
  217.     int    token, tokenlen;
  218.     CHAR    tokenbuf[MAXNAME];
  219.     int    oldtokenlen;
  220.     CHAR    oldtokenbuf[MAXNAME];
  221.     ParseTree *t, *n, *leftn;
  222.  
  223.     token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen);
  224.     switch(token)
  225.     {
  226.     case    '{':    /* (exp) */
  227.         if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  228.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) != '}') {
  229.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  230.             destroy_tree(t);
  231.             return (NULL);
  232.         }
  233.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return t;
  234.         switch(token)
  235.         {
  236.         /* must find boolean infix operator */
  237.         case ',':
  238.         case ';':
  239.             leftn = t;
  240.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  241.             n = (ParseTree *)malloc(sizeof(ParseTree));
  242.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  243.             n->type = INTERNAL;
  244.             n->data.internal.left = leftn;
  245.             n->data.internal.right = t;
  246.             return n;
  247.  
  248.         /* or end of parent sub expression */
  249.         case '}':
  250.             unget_token_bool(bufptr, tokenlen);    /* part of someone else who called me */
  251.             return t;
  252.  
  253.         default:
  254.             destroy_tree(t);
  255.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  256.             return NULL;
  257.         }
  258.  
  259.     /* Go one level deeper */
  260.     case    '~':    /* not exp */
  261.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return NULL;
  262.         switch(token)
  263.         {
  264.         case 'a':
  265.             if (*pnum_terminals >= MAXNUM_PAT) {
  266.                 fprintf(stderr, "Pattern expression too large (> %d)\n", MAXNUM_PAT);
  267.                 return NULL;
  268.             }
  269.             n = &terminals[*pnum_terminals];
  270.             n->op = 0;
  271.             n->type = LEAF;
  272.             n->terminalindex = (*pnum_terminals);
  273.             n->data.leaf.attribute = 0;
  274.             n->data.leaf.value = (unsigned char*)malloc(tokenlen + 2);
  275.             memcpy(n->data.leaf.value, tokenbuf, tokenlen);
  276.             n->data.leaf.value[tokenlen] = '\0';
  277.             (*pnum_terminals)++;
  278.             n->op |= NOTPAT;
  279.             t = n;
  280.             break;
  281.  
  282.         case '{':
  283.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  284.             if (t->op & NOTPAT) t->op &= ~NOTPAT;
  285.             else t->op |= NOTPAT;
  286.             if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) != '}') {
  287.                 fprintf(stderr, "parse error at offset %d\n", *bufptr);
  288.                 destroy_tree(t);
  289.                 return NULL;
  290.             }
  291.             break;
  292.  
  293.         default:
  294.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  295.             return NULL;
  296.         }
  297.         /* The resulting tree is in t. Now do another lookahead at this level */
  298.  
  299.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return t;
  300.         switch(token)
  301.         {
  302.         /* must find boolean infix operator */
  303.         case ',':
  304.         case ';':
  305.             leftn = t;
  306.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  307.             n = (ParseTree *)malloc(sizeof(ParseTree));
  308.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  309.             n->type = INTERNAL;
  310.             n->data.internal.left = leftn;
  311.             n->data.internal.right = t;
  312.             return n;
  313.  
  314.         case '}':
  315.             unget_token_bool(bufptr, tokenlen);
  316.             return t;
  317.  
  318.         default:
  319.             destroy_tree(t);
  320.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  321.             return NULL;
  322.         }
  323.  
  324.     case    'a':    /* individual term (attr=val) */
  325.         if (tokenlen == 0) return NULL;
  326.         memcpy(oldtokenbuf, tokenbuf, tokenlen);
  327.         oldtokenlen = tokenlen;
  328.         token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen);
  329.         switch(token)
  330.         {
  331.         case '}':    /* part of case '{' above: else syntax error not detected but semantics ok */
  332.             unget_token_bool(bufptr, tokenlen);
  333.         case 'e':    /* endof input */
  334.         case ',':
  335.         case ';':
  336.             if (*pnum_terminals >= MAXNUM_PAT) {
  337.                 fprintf(stderr, "Pattern expression too large (> %d)\n", MAXNUM_PAT);
  338.                 return NULL;
  339.             }
  340.             n = &terminals[*pnum_terminals];
  341.             n->op = 0;
  342.             n->type = LEAF;
  343.             n->terminalindex = (*pnum_terminals);
  344.             n->data.leaf.attribute = 0;
  345.             n->data.leaf.value = (unsigned char*)malloc(oldtokenlen + 2);
  346.             memcpy(n->data.leaf.value, oldtokenbuf, oldtokenlen);
  347.             n->data.leaf.value[oldtokenlen] = '\0';
  348.             (*pnum_terminals)++;
  349.             if ((token == 'e') || (token == '}')) return n;    /* nothing after terminal in expression */
  350.  
  351.             leftn = n;
  352.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  353.             n = (ParseTree *)malloc(sizeof(ParseTree));
  354.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  355.             n->type = INTERNAL;
  356.             n->data.internal.left = leftn;
  357.             n->data.internal.right = t;
  358.             return n;
  359.  
  360.         default:
  361.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  362.             return NULL;
  363.         }
  364.  
  365.     case    'e':    /* can't happen as I always do a lookahead above and return current tree if e */
  366.     default:
  367.         fprintf(stderr, "parse error at offset %d\n", *bufptr);
  368.         return NULL;
  369.     }
  370. }
  371.  
  372. int
  373. asplit_pattern(APattern, AM, terminals, pnum_terminals, pAParse)
  374.     CHAR    *APattern;
  375.     int    AM;
  376.     ParseTree terminals[];
  377.     int    *pnum_terminals;
  378.     ParseTree **pAParse;
  379. {
  380.     int    bufptr = 0, ret, i, j;
  381.  
  382.     if (is_complex_boolean(APattern, AM)) {
  383.         AComplexBoolean = 1;
  384.         *pnum_terminals = 0;
  385.         if ((*pAParse = aparse_tree(APattern, AM, &bufptr, terminals, pnum_terminals)) == NULL)
  386.             return -1;
  387.         /* print_tree(*pAParse, 0); */
  388.         return *pnum_terminals;
  389.     }
  390.     else {
  391.         for (i=0; i<AM; i++) {
  392.             if (APattern[i] == '\\') i++;
  393.             else if ((APattern[i] == '{') || (APattern[i] == '}')) {
  394.                 /* eliminate it from pattern by shifting (including '\0') since agrep must essentially do a flat search */
  395.                 for (j=i; j<AM; j++)
  396.                     APattern[j] = APattern[j+1];
  397.                 AM --;
  398.             }
  399.         }
  400.  
  401.         AComplexBoolean = 0;
  402.         *pnum_terminals = 0;
  403.         if ((ret = asplit_pattern_flat(APattern, AM, terminals, pnum_terminals, (int *)pAParse)) == -1)
  404.             return -1;
  405.         return ret;
  406.     }
  407. }
  408.  
  409. /*
  410. int
  411. dd(b, e)
  412.     char    *b, *e;
  413. {
  414.     int    i=0;
  415.     extern int anum_terminals;
  416.     extern char amatched_terminals[];
  417.     for(;i<anum_terminals; i++) printf("%d ", amatched_terminals[i]);
  418.     putchar(':');
  419.     while (b != e) putchar(*b++);
  420.     putchar('\n');
  421.     return 1;
  422. }
  423. */
  424.  
  425. /* fast interpreter for the tree using which terminals matched: array bound checks are not done: its recursive */
  426. int
  427. eval_tree(tree, matched_terminals)
  428.     ParseTree    *tree;
  429.     char        matched_terminals[];
  430. {
  431.     int    res;
  432.     if (tree == NULL) {
  433.         fprintf(stderr, "Eval on empty tree: returning true\n");
  434.         return 1;    /* safety sake, but cannot happen! */
  435.     }
  436.     if (tree->type == LEAF) return ((tree->op & NOTPAT) ? (!matched_terminals[tree->terminalindex]) : (matched_terminals[tree->terminalindex]));
  437.     else if (tree->type == INTERNAL) {
  438.         if ((tree->op & OPMASK) == ANDPAT) {    /* sequential evaluation */
  439.             if ((res = eval_tree(tree->data.internal.left, matched_terminals)) != 0) res = eval_tree(tree->data.internal.right, matched_terminals);
  440.             return (tree->op & NOTPAT) ? !res : res;
  441.         }
  442.         else {    /* sequential evaluation */
  443.             if ((res = eval_tree(tree->data.internal.left, matched_terminals)) == 0) res = eval_tree(tree->data.internal.right, matched_terminals);
  444.             return (tree->op & NOTPAT) ? !res : res;
  445.         }
  446.     }
  447.     else {
  448.         fprintf(stderr, "Eval on bad tree: returning false\n");
  449.         return 0;    /* safety sake, but cannot happen! */
  450.     }
  451. }
  452.  
  453. /* [first, last) = C-style range for which we want the words in terminal-values' patterns: 0..num_terminals for !ComplexBoolean, term/term otherwise */
  454. asplit_terminal(first, last, pat_buf, pat_ptr)
  455.     int    first, last;
  456.     char    *pat_buf;
  457.     int    *pat_ptr;
  458. {
  459.         int    word_length;
  460.         int    type;
  461.     int    num_pat;
  462.  
  463.     *pat_ptr = 0;
  464.     num_pat = 0;
  465.  
  466.     for (; first<last; first++) {
  467.         word_length = strlen(aterminals[first].data.leaf.value);
  468.         if (word_length <= 0) continue;
  469.         if ((type = checksg(aterminals[first].data.leaf.value, D, 0)) == -1) return -1;
  470.         if (!type) return -1;
  471.         strcpy(&pat_buf[*pat_ptr], aterminals[first].data.leaf.value);
  472.         pat_buf[*pat_ptr + word_length] = '\n';
  473.         pat_buf[*pat_ptr + word_length + 1] = '\0';
  474.         *pat_ptr += (word_length + 1);
  475.         num_pat ++;
  476.         if(num_pat >= MAXNUM_PAT) {
  477.             fprintf(stderr, "Warning: too many words in pattern (> %d): ignoring...\n", MAXNUM_PAT);
  478.             break;
  479.         }
  480.     }
  481.     return num_pat;
  482. }
  483.